package leetcode每日一题;

/**
 * 1. 问题描述
 *      编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。
 *      如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处
 *      于“右半部分”即可，其不需要被置于左右两部分之间。
 *
 * 2. 算法分析
 *      创建两个新的链表，按照如下方式连接节点：
 *          如果当前head指向的节点的val < x,则添加到第一个链表上，反之添加到第二个链表上
 *      由题意知道采用头插法添加节点到链表上
 *
 * 3. 代码实现
 */



@SuppressWarnings("all")
public class 分割链表 {

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode front = new ListNode(0);
        ListNode back = new ListNode(0);
        ListNode curf = front;
        // 此时需要使用头插法
        while(head != null) {
            ListNode temp = new ListNode(head.val);
            if(temp.val < x) {
                temp.next = front.next;
                front.next = temp;
            } else {
                temp.next = back.next;
                back.next = temp;
            }
            head = head.next;
        }
        while(curf.next != null) {
            curf = curf.next;
        }
        curf.next = back.next;
        return front.next;
    }

}
